Fixed Segments tree in notebook

[andmenj-acm.git] / Mi manual de algoritmos / version_maraton_suramericana_2008 / #manual.tex#

\documentclass[10pt,letterpaper]{article}

%---------------------------------------------------------------
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{hyperref}
%\usepackage{color}
%---------------------------------------------------------------

\setlength{\topmargin}{-1.0in}
\setlength{\textheight}{9.5in} 
\setlength{\evensidemargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\textwidth}{6.5in} 

\begin{document}

%---------------------------------------------------------------
\title{Resumen de algoritmos para torneos de programación}
\author{Andrés Mejía}
\date{\today}
\maketitle
%---------------------------------------------------------------

%---------------------------------------------------------------
\tableofcontents
%\lstlistoflistings
\lstloadlanguages{C++}
%---------------------------------------------------------------
%---------------------------------------------------------------
\section{Teoría de números}
%---------------------------------------------------------------
\subsection{Big mod}
\input{./src/number_theory/bigmod}%.tex

\subsection{Criba de Eratóstenes}
\small
\textbf{Field-testing:} 
\begin{itemize}
\item \emph{SPOJ} -  2912 - Super Primes
\item \emph{Live Archive} - 3639 - Prime Path
\end{itemize}

\normalsize
Marca los números primos en un arreglo. Algunos tiempos de ejecución:
\begin{center}
\begin{tabular}{c c}
\hline\hline
SIZE & Tiempo (s) \\ [0.5ex]
\hline
100000 & 0.003 \\
1000000 & 0.060 \\
10000000 & 0.620 \\
100000000 & 7.650 \\ [1ex]
\hline
\end{tabular}
\end{center}

\input{./src/number_theory/criba}%.tex

\subsection{Divisores de un número}
Este algoritmo imprime todos los divisores de un número (en desorden) en O($\sqrt{n}$).
Hasta 4294967295 (máximo \textit{unsigned long}) responde instantaneamente. Se puede
forzar un poco más usando \textit{unsigned long long} pero más allá de $10^{12}$ empieza a
responder muy lento.

\bigskip

\input{./src/number_theory/divisores}%.tex

\section{Combinatoria}
\subsection{Cuadro resumen}
Fórmulas para combinaciones y permutaciones:
\begin{center}
\renewcommand{\arraystretch}{2} %Multiplica la altura de cada fila de la tabla por 2
%Si quiero aumentar el tamaño de una fila en particular insertar \rule{0cm}{1cm} en esa fila.
\begin{tabular}{| c | c | c |}
\hline
\textit{Tipo} & \textit{¿Se permite la repetición?} & \textit{Fórmula} \\ [1.5ex]
\hline\hline

$r$-permutaciones & No & $ \displaystyle\frac{n!}{(n-r)!} $ \\ [1.5ex]
\hline
$r$-combinaciones & No & $ \displaystyle\frac{n!}{r!(n-r)!} $ \\  [1.5ex]
\hline
$r$-permutaciones & Sí & $ \displaystyle n^{r} $ \\
\hline
$r$-combinaciones & Sí & $ \displaystyle\frac{(n+r-1)!}{r!(n-1)!} $ \\ [1.5ex]
\hline
\end{tabular}
\renewcommand{\arraystretch}{1}
\end{center}
Tomado de \textit{Matemática discreta y sus aplicaciones}, Kenneth Rosen, 5${}^{\hbox{ta}}$ edición, McGraw-Hill, página 315.

\subsection{Combinaciones, coeficientes binomiales, triángulo de Pascal}
\emph{Complejidad:} $ O(n^2) $ \\
$$ {n \choose k} = \left\{
\begin{array}{c l}
 1 & k = 0\\
 1 & n = k\\
 \displaystyle {n - 1 \choose k - 1} + {n - 1 \choose k} & \mbox{en otro caso}\\
\end{array}
\right.
$$

\input{./src/combinatoria/pascal_triangle}%.tex

\bigskip 
\textbf{Nota:} $ \displaystyle {n \choose k }  $ está indefinido en el código anterior si $ n > k$. ¡La tabla puede estar llena con cualquier basura del compilador!

\subsection{Permutaciones con elementos indistinguibles}
El número de permutaciones \underline{diferentes} de $n$ objetos, donde hay $n_{1}$ objetos indistinguibles de tipo 1,
$n_{2}$ objetos indistinguibles de tipo 2, ..., y $n_{k}$ objetos indistinguibles de tipo $k$, es
$$
\frac{n!}{n_{1}!n_{2}! \cdots n_{k}!}
$$
\textbf{Ejemplo:} Con las letras de la palabra \texttt{PROGRAMAR} se pueden formar $ \displaystyle \frac{9!}{2! \cdot 3!} = 
30240 $ permutaciones \underline{diferentes}.
\subsection{Desordenes, desarreglos o permutaciones completas}

Un desarreglo es una permutación donde ningún elemento $i$ está en la
posición $i$-ésima. Por ejemplo, \textit{4213} es un desarreglo de 4 elementos pero
\textit{3241} no lo es porque el 2 aparece en la posición 2.

Sea $D_{n}$ el número de desarreglos de $n$ elementos, entonces:
$$ {D_{n}} = \left\{
\begin{array}{c l}
 1 & n = 0\\
 0 & n = 1\\
 (n-1)(D_{n-1} + D_{n-2}) & n \geq 2\\
\end{array}
\right.
$$
Usando el principio de inclusión-exclusión, también se puede encontrar la fórmula
$$
D_{n} = n!\left [ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^{n}\frac{1}{n!} \right ]
= n! \sum_{i=0}^{n} \frac{(-1)^{i}}{i!}
$$

\section{Grafos}
\subsection{Algoritmo de Dijkstra}
El peso de todas las aristas debe ser no negativo.
\\
\input{./src/grafos/dijkstra}%.tex

\subsection{Minimum spanning tree: Algoritmo de Prim}

\input{./src/grafos/prim}%.tex

\subsection{Minimum spanning tree: Algoritmo de Kruskal + Union-Find}
\input{./src/grafos/kruskal}%.tex

\subsection{Algoritmo de Floyd-Warshall}
\emph{Complejidad:} $ O(n^3) $ \\
Se asume que no hay ciclos de costo negativo.
\input{./src/grafos/floyd}%.tex

\subsection{Algoritmo de Bellman-Ford}
Si no hay ciclos de coste negativo, encuentra la distancia más corta entre un nodo
y todos los demás. Si sí hay, permite saberlo. \\
El coste de las aristas \underline{sí} puede ser negativo.
\input{./src/grafos/bellman}%.tex

\subsection{Puntos de articulación}
\input{./src/grafos/puntos_articulacion}%.tex

\subsection{Máximo flujo: Método de Ford-Fulkerson, algoritmo de Edmonds-Karp}
El algoritmo de Edmonds-Karp es una modificación al método de Ford-Fulkerson. Este último
utiliza DFS para hallar un camino de aumentación, pero la sugerencia de Edmonds-Karp
es utilizar BFS que lo hace más eficiente en algunos grafos.
\medskip

\input{./src/grafos/ford_fulkerson}%.tex

\section{Programación dinámica}
\subsection{Longest common subsequence}
\input{./src/dp/lcs}%.tex

\subsection{Partición de troncos}
Este problema es similar al problema de \textit{Matrix Chain Multiplication}. Se tiene
un tronco de longitud $n$, y $m$ puntos de corte en el tronco. Se puede hacer un corte a la vez,
cuyo costo es igual a la longitud del tronco. ¿Cuál es el mínimo costo para partir todo el tronco
en pedacitos individuales?
\\
\medskip
\textbf{Ejemplo:} Se tiene un tronco de longitud 10. Los puntos de corte son 2, 4, y 7. El mínimo
costo para partirlo es 20, y se obtiene así:
\begin{itemize}
\item Partir el tronco (0, 10) por 4. Vale 10 y quedan los troncos (0, 4) y (4, 10).
\item Partir el tronco (0, 4) por 2. Vale 4 y quedan los troncos (0, 2), (2, 4) y (4, 10).
\item No hay que partir el tronco (0, 2).
\item No hay que partir el tronco (2, 4).
\item Partir el tronco (4, 10) por 7. Vale 6 y quedan los troncos (4, 7) y (7, 10).
\item No hay que partir el tronco (4, 7).
\item No hay que partir el tronco (7, 10).
\item El costo total es $10+4+6 = 20$.
\end{itemize}

\medskip
El algoritmo es $O(n^3)$, pero optimizable a $O(n^2)$ con una tabla adicional:
\input{./src/dp/particion_troncos}%.tex

\section{Geometría}
\subsection{Área de un polígono}
Si P es un polígono simple (no se intersecta a sí mismo) su área está dada por: \\

$ A(P) = \frac{1}{2} \displaystyle\sum_{i=0}^{n-1} (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $ \\
\bigskip
\input{./src/geometria/polygon_area}%.tex

\subsection{Centro de masa de un polígono}
Si P es un polígono simple (no se intersecta a sí mismo) su centro de masa está dado por: \\

$ \displaystyle\bar{C}_{x} = \frac{ \displaystyle\iint_{R} x \, dA }{M} = \frac{1}{6M}\sum_{i=1}^{n} (y_{i+1} - y_{i}) (x_{i+1}^2 + x_{i+1} \cdot x_{i} + x_{i}^2) $

\medskip

$\displaystyle\bar{C}_{y} = \frac{ \displaystyle\iint_{R} y \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (x_{i} - x_{i+1}) (y_{i+1}^2 + y_{i+1} \cdot y_{i} + y_{i}^2)$

\medskip

Donde $ M $ es el área del polígono. \\

Otra posible fórmula equivalente:

$ \displaystyle\bar{C}_{x} = \frac{1}{6A} \sum_{i=0}^{n-1} (x_{i} + x_{i+1}) (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $

\medskip

$ \displaystyle\bar{C}_{y} = \frac{1}{6A} \sum_{i=0}^{n-1} (y_{i} + y_{i+1}) (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $


\subsection{Convex hull: Graham Scan}
\emph{Complejidad:} $ O(n \log_{2}{n}) $
\input{./src/geometria/grahamscan}%.tex

\subsection{Convex hull: Andrew's monotone chain}
\emph{Complejidad:} $ O(n \log_{2}{n}) $
\input{./src/geometria/monotonechain}%.tex

\subsection{Mínima distancia entre un punto y un segmento}
\input{./src/geometria/distance_point_to_segment}%.tex

\subsection{Mínima distancia entre un punto y una recta}
\input{./src/geometria/distance_point_to_line}%.tex

\subsection{Determinar si un polígono es convexo}
\input{./src/geometria/is_convex_polygon}%.tex

\subsection{Determinar si un punto está dentro de un polígono convexo}
\input{./src/geometria/is_inside_convex_polygon}%.tex

\subsection{Determinar si un punto está dentro de un polígono cualquiera}
\small
\textbf{Field-testing:} 
\begin{itemize}
\item \emph{TopCoder} -  SRM 187 - Division 2 Hard - PointInPolygon
\end{itemize}
\input{./src/geometria/is_inside_concave_polygon}%.tex

%---------------------------------------------------------------
\section{Estructuras de datos}
\subsection{Árboles de Fenwick ó Binary indexed trees}

Se tiene un arreglo $\{a_0, a_1, \cdots, a_{n-1}\}$. Los árboles
de Fenwick permiten encontrar $ \displaystyle \sum_{k=i}^{j} a_k $ en orden $O(\log_{2}{n})$ para parejas de $(i, j)$ con $i \leq j$. De la misma manera, permiten sumarle una cantidad a un $a_i$ también en tiempo $O(log_{2}{n})$.
\medskip
\input{./src/estructuras/fenwick}%.tex

\subsection{Segment tree}
\input{./src/estructuras/segment_tree}%.tex

%---------------------------------------------------------------
\section{Misceláneo}
\subsection{El \textit{parser} más rápido del mundo}
\begin{itemize}
\item Cada no-terminal: un método
\item Cada lado derecho: 
\begin{itemize}
\item invocar los métodos de los no-terminales o
\item Cada terminal: invocar proceso \textit{match}
\end{itemize}
\item Alternativas en una producción: se hace un \textit{if}
\end{itemize}
\medskip
No funciona con gramáticas recursivas por izquierda ó en las que en algún momento haya
varias posibles escogencias que empiezan por el mismo caracter (En ambos casos la gramática se puede factorizar).

\medskip
\textbf{Ejemplo:} Para la gramática:
$$
A \longrightarrow (A)A 
$$ $$
A \longrightarrow \epsilon
$$

\input{./src/misc/parser_recursivo_desc}%.tex


\section{Java}
\subsection{Entrada desde entrada estándar}
Este primer método es muy fácil pero es mucho más ineficiente porque utiliza Scanner en vez de BufferedReader: \\
\input{./src/java/io_estandar_easy}%.tex

\bigskip

Este segundo es más rápido: \\
\input{./src/java/io_estandar}%.tex
\subsection{Entrada desde archivo}
\input{./src/java/io_file}%.tex

\subsection{Mapas y sets}
Programa de ejemplo:
\input{./src/java/maps_sets}%.tex
\bigskip
La salida de este programa es: \\

\ttfamily 
\fbox{\parbox{2.0in}{
Maps\\
m.size() = 1\\
465\\
null\\
\\
Sets\\
54 presente.\\
s.size() = 3\\
54\\
3576\\
1000000007\\
s.size() = 0\\
}
}
\\ \normalfont\normalsize
\bigskip 
Si quiere usarse una clase propia como llave del mapa o como elemento del set, la clase debe implementar
algunos métodos especiales: Si va a usarse un TreeMap ó TreeSet hay que implementar los métodos \texttt{compareTo} y 
\texttt{equals} de la interfaz \texttt{Comparable} como en la sección \ref{colas_de_prioridad_java}. Si va a usarse
un HashMap ó HashSet hay más complicaciones.\\
\smallskip
\textbf{Sugerencia:} Inventar una manera de codificar y decodificar la clase en una String o un Integer y meter esa representación en el mapa o set: esas clases ya tienen los métodos implementados.

\subsection{Colas de prioridad}
\label{colas_de_prioridad_java}
Hay que implementar unos métodos. Veamos un ejemplo: \\
\input{./src/java/priority_queue}%.tex
\bigskip
La salida de este programa es: \\

\ttfamily 
\fbox{\parbox{2.0in}{
peso = 0, destino = 12\\
peso = 0, destino = 8\\
peso = 0, destino = 13\\
peso = 3, destino = 7\\
peso = 1876, destino = 4\\
}
}
\\ \normalfont\normalsize
\medskip
Vemos que la función de comparación que definimos no tiene en cuenta \texttt{destino},
por eso no desempata cuando dos \texttt{Items} tienen el mismo \texttt{peso} si no que escoge
cualquiera de manera arbitraria.

\section{C++}
\subsection{Entrada desde archivo}
\input{./src/c++/io_file}%.tex

\subsection{Strings con caractéres especiales}
\input{./src/c++/unicode}%.tex

\emph{Nota}: Como alternativa a la función getline, se pueden utilizar las funciones fgetws y fputws, y más adelante swscanf y wprintf:
\input{./src/c++/fgetws}%.tex

\end{document}